package JZOffer;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 剑指 Offer 03. 数组中重复的数字
 * 找出数组中重复的数字。
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 * 数组中某些数字是重复的，
 * 但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 * **/

//暴力解法
    //遍历数组中的每个元素，然后在剩下的元素中寻找是否存在相同的元素
class Solution03_1 {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j <nums.length; j++){
                if (nums[i] == nums[j]){
                    return nums[i];
                }
            }
        }
        return -1;
    }
}

//哈希查找
//在暴力解法中，我们先遍历每一个元素，然后再从其余的元素中查找这个元素是否存在，其实这里要的就是能高效的判断一个元素是否已经存在，
// 我们可以使用哈希表，因为哈希表判断是否存在的时间复杂度是 O(1)。

class Solution03_2{
    public int findRepeatNumber(int[] nums){
        //初始化一个哈希表
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            //判断当前元素是否已经存在
            if (set.contains(nums[i])){
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }
}

//数组代替哈希表
class Solution03_3 {
    public int findRepeatNumber(int[] nums){
        int[] bucker = new int[nums.length];
        Arrays.fill(bucker, -1);

        for (int i = 0; i < nums.length; i++){
            if (bucker[nums[i]] != -1){
                return nums[i];
            }

            bucker[nums[i]] = i;
        }
        return -1;
    }
}

//最优解法
class Solution03_4 {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (i != nums[i]) {

                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }

                // 交换
                int tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }

        return -1;
    }

}